/**
 * 
 */
package string.passed2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class GenerateParentheses {

	/**
	 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
	
	For example, given n = 3, a solution set is:
	
	"((()))", "(()())", "(())()", "()(())", "()()()"
	 */
	public List<String> generateParenthesis(int n) {
		List<String> solutions = new ArrayList<String>();
		generateParenthesis(n, n, solutions, new StringBuilder());
		//generateParenthesis(0, 0, 0, n, list, new StringBuilder());
		return solutions;
	}

	private void generateParenthesis(int left, int right,
			List<String> solutions, StringBuilder solution) {
		if (left == 0 && right == 0) {
			solutions.add(solution.toString());
		} else {
			if (left > 0) {
				solution.append('(');
				generateParenthesis(left - 1, right, solutions, solution);
				solution.setLength(solution.length() - 1);
			}
			if (right > left) {
				solution.append(')');
				generateParenthesis(left, right - 1, solutions, solution);
				solution.setLength(solution.length() - 1);
			}
		}

	}

	//Good for interview
    private void generateParenthesisHelper(int left, int right, int n, StringBuilder solution, List<String> solutions) {
        if (left == n && right == n) {
            solutions.add(solution.toString());
            return;
        }
        else if (left > n || right > left) {
            return;
        }
        
        solution.append('(');
        generateParenthesisHelper(left + 1, right, n, solution, solutions);
        solution.setLength(solution.length() - 1);
        solution.append(')');
        generateParenthesisHelper(left, right + 1, n, solution, solutions);
        solution.setLength(solution.length() - 1);
    }
	
	private void generateParenthesis(int left, int right, int n,
			List<String> solutions, StringBuilder solution) {
		if (left == n && right == n) {
			solutions.add(solution.toString());
		} else {
			if (left < n) {
				solution.append('(');
				generateParenthesis(left + 1, right, n, solutions, solution);
				solution.setLength(solution.length() - 1);
			}

			if (right < left) {
				solution.append(')');
				generateParenthesis(left, right + 1, n, solutions, solution);
				solution.setLength(solution.length() - 1);
			}
		}
	}

	/**
	 * 
	 */
	public GenerateParentheses() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 3;
		GenerateParentheses gp = new GenerateParentheses();
		List<String> list = gp.generateParenthesis(n);
		for (String s : list) {
			System.out.println(s);
		}

	}

}
